package problems.contest;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @author dubulingbo, 2023/05/14, 014 16:11.
 */
public class WCT345 {
    /**
     * T1|6430.找出转圈游戏输家
     * <p>https://leetcode.cn/problems/find-the-losers-of-the-circular-game/</p>
     */
    public int[] circularGameLosers(int n, int k) {
        boolean[] f = new boolean[n];
        int no = 0;
        int i = 1;
        while (!f[no]) {
            f[no] = true;
            no = (no + i * k) % n;
            ++i;
        }

        int cnt = 0;
        for (boolean b : f) cnt += b ? 0 : 1;

        int[] ans = new int[cnt];
        i = 0;
        for (int j = 0; j < n; ++j) {
            if (!f[j]) {
                ans[i++] = j + 1;
            }
        }

        return ans;
    }

    /**
     * T2|6431.相邻值的按位异或
     * <p>https://leetcode.cn/problems/neighboring-bitwise-xor/</p>
     */
    public boolean doesValidArrayExist(int[] derived) {
        int n = derived.length;
        int[] original = new int[n];

        // 枚举 original[0] = 0 或者 original[0] = 1
        // 只要有一个满足条件，则说明可以找到 original 数组
        if (helper(original, derived)) {
            return true;
        }
        original[0] = 1;
        return helper(original, derived);
    }

    private boolean helper(int[] original, int[] derived) {
        int n = original.length;
        for (int i = 0; i < n - 1; ++i) {
            original[i + 1] = original[i] ^ derived[i];
        }
        return (original[n - 1] ^ original[0]) == derived[n - 1];
    }


    /**
     * T3|6433.矩阵中移动的最大次数
     * <p>https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/</p>
     */
    public int maxMoves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] d = {-1, 0, 1};
        // 每一列进行遍历
        int[] vis = new int[m];
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < m; ++i) que.offer(i);
        Arrays.fill(vis, -1);
        for (int i = 0; i < n - 1; ++i) {

            for (int j = que.size(); j > 0 ; --j) {
                int cur = que.poll();
                for (int k : d) {
                    if (cur + k >= 0 && cur + k < m && vis[cur + k] != i && grid[cur + k][i + 1] > grid[cur][i]) {
                        vis[cur + k] = i;
                        que.offer(cur + k);
                    }
                }
            }

            if (que.size() == 0) return i;
        }

        return n - 1;
    }
}
